package 牛客网在线编程题库;

/**
 * 请实现有重复数字的升序数组的二分查找
 给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1
 示例1
 输入
 复制
 [1,2,4,4,5],4
 返回值
 复制
 2
 说明
 从左到右，查找到第1个为4的，下标为2，返回2
 示例2
 输入
 复制
 [1,2,4,4,5],3
 返回值
 复制
 -1
 示例3
 输入
 复制
 [1,1,1,1,1],1
 返回值
 复制
 0
 */

public class _二分查找 {
    public static void main(String[] args) {
        // 1
        int[] nums = {1, 2, 2, 3, 4};
        int target = 2;
        int result = search1(nums, target);
        System.out.println(result);
    }

    /**
     * 适用于数组中无重复数字
     * @param nums
     * @param target
     * @return
     */
    public static int search (int[] nums, int target) {
        // write code here
        // 定义返回目标数值
        int result = -1;
        // 定义首尾，中间指针
        int low = 0, high = nums.length - 1;
        int mid;
        // 当头指针在尾指针左边时
        while (low <= high) {
            // 初始化中间指针
            mid = low + (high - low) / 2;
            // 将中间值与目标值比较
            if (nums[mid] < target) {
                low = mid + 1;
            }else if (nums[mid] > target) {
                high = mid - 1;
            }else {
                result = mid;
                break;
            }
        }
        return result;
    }

    /**
     * 适用于数组中有重复数字
     * @param nums
     * @param target
     * @return
     */
    public static int search1 (int[] nums, int target) {
        // write code here
        // 定义返回目标数值
        int result = -1;
        // 定义首尾，中间指针
        int low = 0, high = nums.length - 1;
        int mid;
        // 当头指针在尾指针左边时
        while (low <= high) {
            // 初始化中间指针
            mid = low + (high - low) / 2;
            // 将中间值与目标值比较
            if (nums[mid] < target) {
                low = mid + 1;
            }else if (nums[mid] > target) {
                high = mid - 1;
            }else {
                // 有重复数字出现的情况，则要进行进一步判断该数字是不是第一个出现
                if (mid == 0 || nums[mid - 1] != target) {
                    result = mid;
                    break;
                }else {
                    high = mid - 1;
                }
            }
        }
        return result;
    }
}
